package 树;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 *
 * 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
 */
public class _173_二叉搜索树迭代器 {
   public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    class BSTIterator {
       private int index; //索引，用于获取元素，判断是否还有元素
       private List<Integer> list; //存放对二叉树进行中序遍历的结果

        public BSTIterator(TreeNode root) {
            index = 0;
            list = new ArrayList<>();
            inOrderTraversal(root,list); //初始化的时候就进行遍历并将遍历结果放到list中
        }

        public int next() {
            return list.get(index++); //取出中序遍历后存放在list数组中的元素
        }

        public boolean hasNext() {
            return index < list.size();
        }

        //对二叉树进行中序遍历 左 根 右
        private void inOrderTraversal(TreeNode node,List<Integer> list){
            if(node == null) return;

            inOrderTraversal(node.left,list);
            list.add(node.val);
            inOrderTraversal(node.right,list);

        }
    }
}
